from typing import *


class Solution:

    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        ans = [0, 0, 0]
        x = [[0] * n for _ in range(m)]
        y = [[0] * n for _ in range(n)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if matrix[i][j] == 0:
                    x[i][j] = x[i][j + 1] + 1 if j + 1 < n else 1
                    y[i][j] = y[i + 1][j] + 1 if i + 1 < m else 1
        for i in range(m):
            for j in range(n):
                for k in range(ans[2] + 1, min(m - i + 1, n - j + 1)):
                    if x[i][j] >= k and x[i + k -
                                          1][j] >= k and y[i][j] >= k and y[i][
                                              j + k - 1] >= k:
                        ans = [i, j, k]

        return ans if ans[2] > 0 else []


s = Solution()
print(s.findSquare([[1, 0, 1], [0, 0, 1], [0, 0, 1]]))
